package com.leetcode.链表.合并链表;

import com.leetcode.公共.ListNode;

import java.util.ArrayList;
import java.util.PriorityQueue;

/**
 * 给你一个链表数组，每个链表都已经按升序排列。
 * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
 */
public class 合并k个排序链表 {
    // 首元节点
    ListNode head = new ListNode(0);

    /**
     * 思路一：将所有节点添加到一个数组里
     * 在数组里面排序后，再将排好序的节点们重新组成一个链表
     *
     * @param lists
     * @return
     */
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        // 将所有节点放到一个数组里面
        ArrayList<ListNode> nodes = new ArrayList<>();
        for (ListNode list : lists) {
            while (list != null) {
                nodes.add(list);
                list = list.next;
            }
        }

        // 对数组进行排序
        nodes.sort((ListNode node1, ListNode node2) -> {
            return node1.val - node2.val;
        });

        // 将排好序的节点串起来
        ListNode head = new ListNode(0);
        ListNode cur = head;
        for (ListNode node : nodes) {
            cur = cur.next = node;
        }

        return head.next;
    }

    /**
     * 思路二：逐一两两合并
     *
     * @param lists
     * @return
     */
    public ListNode mergeKLists2(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        for (int i = 1; i < lists.length; i++) {
            lists[0] = mergeTwoLists(lists[0], lists[i]);
        }
        return lists[0];
    }

    /**
     * 何并两条链表lian biao
     * @param k1
     * @param k2
     * @return
     */
    public ListNode mergeTwoLists(ListNode k1, ListNode k2) {
        if (k1 == null) return k2;
        if (k2 == null) return k1;

        head.next = null;
        ListNode cur = head;
        while (k1 != null && k2 != null) {
            if (k1.val <= k2.val) {
                cur = cur.next = k1;
                k1 = k1.next;
            } else {
                cur = cur.next = k2;
                k2 = k2.next;
            }
        }

        if (k1 == null) {
            cur.next = k2;
        } else {
            cur.next = k1;
        }
        return head.next;
    }

    /**
     * 思路三：使用优先级队列，小顶堆
     *
     * @param lists
     * @return
     */
    public ListNode mergeKLists3(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        ListNode head = new ListNode(0);
        ListNode cur = head;

        PriorityQueue<ListNode> queue = new PriorityQueue<>((ListNode node1, ListNode node2) -> {
            return node1.val - node2.val;
        });
        // 把所有元素加入小顶堆
        for (ListNode list : lists) {
            if (list == null) continue;
            queue.offer(list);
        }
        // 不断删除堆顶元素
        while (!queue.isEmpty()) {
            ListNode node = queue.poll();
            cur = cur.next = node;
            if (node.next != null){
                queue.offer(node.next);
            }
        }

        return head.next;
    }

    /**
     * 思路四：分治策略（效率最好）
     *
     * @param lists
     * @return
     */
    public ListNode mergeKLists4(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        int step = 1;
        while (step < lists.length){
            int nextStep = step << 1;
            for (int i = 0; i + step < lists.length; i += nextStep){
               lists[i] = mergeTwoLists(lists[i], lists[i + step]);
            }
            step = nextStep;
        }
        return lists[0];
    }
}
